package com.github.hgkmail.hello.leetcode101.dp.oned;

import java.util.Arrays;

//一维(one-d)数组动态规划
//常见解题切入点：dp[i]表示以[第i位结尾]的子数组的结果
//打家劫舍：dp[i]=max{ dp[i-1], dp[i-2]+money[i] }
//这种dp数组+迭代的代码是最好的代码，不用再优化。
public class LC198HouseRobber {

    public int rob(int[] nums) {
        int len=nums.length;
        if (len<=0) {
            return 0;
        }
        if (len<=1) {
            return nums[0];
        }
        //dp数组，初始值都是0
        int[] dp=new int[len];
        Arrays.fill(dp, 0);
        //base case
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0], nums[1]);
        //子问题转移方程
        for (int i = 2; i < len; i++) {
            dp[i]=Math.max(dp[i-1], dp[i-2]+nums[i]);
        }
        return dp[len-1];
    }

    //空间压缩（注意不是状态压缩），降低空间复杂度
    public int rob2(int[] nums) {
        int len=nums.length;
        if (len<=0) {
            return 0;
        }
        if (len<=1) {
            return nums[0];
        }
        //定义prev和curr，注意：prev1离curr更近，即 curr->prev1->prev2
        int prev2, prev1, curr=0;
        //base case
        prev2 = nums[0];
        curr=prev1 = Math.max(nums[0], nums[1]);
        //子问题转移方程
        for (int i = 2; i < len; i++) {
            curr = Math.max(prev1, prev2+nums[i]); //prev1更近
            prev2=prev1;
            prev1=curr;
        }
        return curr;
    }

    public static void main(String[] args) {
        System.out.println(new LC198HouseRobber().rob2(new int[]{1,2,3,1}));
    }
}
